import java.util.ArrayList;
import java.util.List;

public class MySingleList {

    //节点类
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode() {

        }
    }

    public ListNode head;

    public void createList() {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);


        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;

        this.head = node1;

    }

    public void show() {
        //不要让head动
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    /**
     * 从指定节点开始进行打印
     * @param newHead
     */
    public void show(ListNode newHead) {
        //不要让head动
        ListNode cur = newHead;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }


    //头插法  时间复杂度O(1)
    public void addFirst(int data){
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }

    //尾插法 时间复杂度O(N)
    public void addLast(int data){
        ListNode node = new ListNode(data);
        if(head == null) {
            head = node;
            return;
        }
        //找尾巴
        ListNode cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }

    //任意位置前面插入,第一个数据节点为0号下标
    public void addIndex(int index,int data){
        int len = size();
        //TODO: 自己实现方法 和 自定义异常
        if(index < 0 || index > len) {
            return;
        }
        //头插法
        if(index == 0) {
            addFirst(data);
            return;
        }
        //尾插法
        if(index == len) {
            addLast(data);
            return;
        }
        //中间位置
        ListNode cur = searchIndex(index);
        if(cur == null) {
            return;
        }
        ListNode node = new ListNode(data);
        node.next = cur.next;
        cur.next = node;
    }

    /**
     * 找到index位置的前一个节点
     * @param index
     * @return
     */
    private ListNode searchIndex(int index) {
        int len = size();
        if(index < 0 || index > len) {
            return null;
        }
        ListNode cur = head;
        int count = 0;
        while (count != index-1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }


    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur = head;
        while (cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点 O(N)
    public void remove(int key) {
        if(head == null) {
            return;
        }
        if(head.val == key) {
            head = head.next;
            return;
        }
        //走到这里 第一个节点 如果是要删除的节点 此时已经删除完毕
        ListNode prev = findNodePrev(key);
        if(prev == null) {
            return;
        }
        /*ListNode del = prev.next;
        prev.next = del.next;*/
        prev.next = prev.next.next;
    }

    /**
     * 查找关键字Key的前驱节点，找到返回地址
     * 找不到返回null         while (prev.next != null) {
     * @param key
     * @return
     */
    private ListNode findNodePrev(int key) {
        if(head == null) {
            return null;
        }
        ListNode prev = head;
        while (prev.next != null) {
            if (prev.next.val == key) {
                return prev;
            }
            prev = prev.next;
        }
        return null;
    }


    //删除所有值为key的节点
    public void removeAllKey(int key){
        if(head == null) {
            return;
        }
        /*while (head != null && head.val == key) {
            head = head.next;
            //return;
        }
        if(head == null) {
            return;
        }*/
        ListNode prev = this.head;
        ListNode cur = head.next;
        while (cur != null) {
            if(cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        if(head.val == key) {
            head = head.next;
        }
    }

    //得到单链表的长度
    public int size(){
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

    public void clear() {
        this.head = null;
    }


    /**
     * 移除数组元素(法一：使用虚拟头节点迭代实现)
     */

    public ListNode removeElements1(ListNode head, int val) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;

        while(temp.next != null) {
            if(temp.next.val == val) {
                temp.next = temp.next.next;//跳过
            }else {
                temp = temp.next;//连接
            }
        }
        return dummyHead.next;
    }

    /**
     * 移除数组元素(法二：不使用虚拟头节点迭代实现)
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements2(ListNode head, int val) {
        //先处理最先的
        while(head != null) {
            if(head.val == val) {
                head = head.next;
            }else {
                break;
            }
        }
        if(head == null) {
            return null;
        }
        ListNode cur = head;
        //处理中间和最后
        while(cur.next != null) {
            //处理中间的
            if(cur.next.val == val) {
                cur.next = cur.next.next;//跳过
            }else {
                cur = cur.next;//连接
            }
        }
        return head;
    }

    /**
     * 移除数组元素(法三：递归实现)
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements3(ListNode head, int val) {
        if(head == null) {
            return null;
        }

        head.next = removeElements3(head.next,val);

        return head.val == val ? head.next : head;
    }

    /**
     * 反转链表（法一：迭代实现,快慢指针）
     * @param head
     * @return
     */
    public ListNode reverseList1(ListNode head){
        if(head == null) {
            return head;
        }
        ListNode cur = head.next;
        head.next = null;
        while(cur != null) {
            ListNode curN = cur.next;
            cur.next = head;
            head = cur;
            cur = curN;
        }
        return head;
    }

    /**
     * 反转链表（法二：递归实现）
     * @param head
     * @return
     */
    public ListNode reverseList2(ListNode head) {
        //返回条件
        if(head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList2(head.next);
        //以下为重复的过程
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    /**
     * 找链表的中间结点（法一：快慢指针）
     * @param head
     * @return
     */
    public ListNode middleNode1(ListNode head) {
        ListNode slow = new ListNode();
        ListNode fast = new ListNode();
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    /**
     * 找链表的中间结点（法二：数组）
     * @param head
     * @return
     */
    public ListNode middleNode2(ListNode head) {
        ListNode[] A = new ListNode[100];
        int t = 0;
        while(head != null) {
            A[t++] = head;
            head = head.next;
        }
        return A[t/2];
    }

    /**
     * 找链表的中间结点（法三：单指针法）
     * @param head
     * @return
     */
    public ListNode middleNode3(ListNode head) {
        int n = 0;
        ListNode cur = head;
        //得知链表长度
        while (cur != null) {
            ++n;
            cur = cur.next;
        }
        int k = 0;
        cur = head;
        while (k < n / 2) {
            ++k;
            cur = cur.next;
        }
        return cur;
    }

    /**
     * 返回倒数第 K 个节点（法一：双指针）
     *
     * @param head
     * @param k
     * @return
     */
    public int KthToLast(ListNode head, int k) {
        ListNode fast = new ListNode();
        ListNode slow = new ListNode();
        for(int i = k-1; k > 0; k--) {
            if(fast == null) {
                break;
            }else {
                fast = fast.next;
            }
        }
        while(fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }

    //递归
    int K = 1;
    public int kthToLast2(ListNode head, int k) {
        //当节点在最末尾时触发返回
        if(head.next == null) {
            return head.val;
        }
        //返回的值
        int val = kthToLast2(head.next,k);
        //一旦触发返回，从第一个产生的位置用 K 计数
        if(K++ >= k) {
            //当达到或超过倒数第 K 时 ， 即 K >= k 时保持返回值不变
            return val;
        }else {
            //没达到则更新需要返回的值
            return head.val;
        }
    }

    //法三：2 次遍历，第一次找到链表的长度 N，第二次遍历N - K次，即可返回。
    public int kthToLast3(ListNode head, int k) {
        int N = 0;
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next;
            N++;
        }

        cur = head;
        for (int i = N - k; i > 0; i--) {
            cur = cur.next;
        }
        return cur.val;
    }

    //法四：用一个集合记录所有的链表元素，返回集合中第 集合长度 - K 个元素
    public int kthToLast4(ListNode head, int k) {
        //用一个集合记录所有的链表元素
        List<ListNode> list = new ArrayList<>();
        while(head != null) {
            list.add(head);
            head = head.next;
        }
        return list.get(list.size() - k).val;
    }

    //合并两个有序链表(法一：迭代)
    public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
        ListNode preHead = new ListNode(-1);//用来定位头的

        ListNode prev = preHead;//移动找到较小结点后连接


        while(l1 != null && l2 != null) {
            if(l1.val <= l2.val) {
                prev.next = l1;//连接
                l1 = l1.next;//移动
            }else {
                prev.next = l2;//连接
                l2 = l2.next;//移动
            }
            prev = prev.next;//移动
        }

        //合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向为合并完的链表即可

        prev.next = l1 == null ? l2 : l1;
        return preHead.next;
    }

    //合并两个有序链表（法二：递归）
    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        if(l1 == null) {
            return l2;
        }else if(l2 == null) {
            return l1;
        }else if(l1.val < l2.val) {
            l1.next = mergeTwoLists2(l1.next,l2);
            return l1;
        }else {
            l2.next = mergeTwoLists2(l1,l2.next);
            return l2;
        }
    }


    //编写代码，以给定值x为基准将链表分割成两部分，所有⼩于x的结点排在⼤于或等于x的结点之前
    public ListNode partition(ListNode pHead, int x) {
        ListNode bs = null;//标记小于 x 的结点的链表的头
        ListNode be = null;//标记小于 x 的结点的链表的尾
        ListNode as = null;//标记不小于 x 的结点的链表的头
        ListNode ae = null;//标记不小于 x 的结点的链表的尾

        ListNode cur = pHead;//用来移动遍历数组

        while(cur != null) {
            if(cur.val < x) {
                if(bs == null) {
                    //这个段当中 第1次插入数据
                    bs = be = cur;//只放进一个结点时，bs 和 be 在同一个位置
                }else {
                    be.next = cur;//连接
                    be = be.next;//令 be = cur,等于尾巴，且第一次也能使 bs.next = be;
                }
            }else {
                if(as == null) {
                    as = ae = cur;
                }else {
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        //以上代码已经遍历完了，分成了 bs 和 as 两个链表
        if(bs == null) {
            //没有 < x 的数据
            return as;
        }
        //以下情况 bs 肯定不为空
        be.next = as;
        //as 不为空
        if(as != null) {
            ae.next = null;
        }
        // 若 as 为空或不为空都得返回 bs
        return bs;
    }


    //验证链表的回⽂结构
    public boolean chkPalindrome(ListNode head) {
        if(head == null) {
            return true;
        }

        //找中间位置
        ListNode fast = head;
        ListNode slow = head;
        //一定得是 && 使得 fast 到链表之外才停下
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        //开始翻转
        //开始翻转 slow 起的后半部分(把这的 slow 看成 head)
        ListNode cur = slow.next;
        while(cur != null) {//注意这是 cur 不是 slow
            ListNode curN = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curN;
        }

        //开始判断是否回文
        //是奇数时，一定会存在 slow == head 的情况
        //是偶数时，一定不会存在 slow == head 的情况，所有需要用 head.next == slow 来约束它停下
        while(slow != head) {
            if(slow.val != head.val) {
                return false;
            }
            if(head.next == slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }

        return true;
    }

    //输⼊两个链表，找出它们的第⼀个公共结点。
    //法一: 使两链表从距离链表尾部同一长度位置开始移动，找到交点
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) {
            return null;
        }

        ListNode pA = headA;
        ListNode pB = headB;

        //分别算出两条链表的长度
        int sizeA = 0;
        int sizeB = 0;
        while(pA != null) {
            sizeA++;
            pA = pA.next;
        }
        while(pB != null) {
            sizeB++;
            pB = pB.next;
        }

        // pA pB 复原，是 pA , pB 链表长度相同
        pA = headA;
        pB = headB;
        if(sizeA > sizeB) {
            for(int i = sizeA - sizeB; i > 0 ; i--) {
                pA = pA.next;
            }
        }else {
            for(int i = sizeB - sizeA; i > 0; i--) {
                pB = pB.next;
            }
        }

        //开始移动
        while(pA != null && pB != null) {
            if(pA == pB) {
                return pA;
            }
            pA = pA.next;
            pB = pB.next;
        }

        return null;
    }


    //法二
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) {
            return null;
        }

        ListNode pA = headA, pB = headB;
        while(pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }



    //给定⼀个链表，判断链表中是否有环。
    /**
     * 快慢指针，如果会相遇就说明存在环(「Floyd 判圈算法」（又称龟兔赛跑算法）)
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        //如果 fast 和 slow 在同一位置，循环进不去
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }


    //给定⼀个链表，返回链表开始⼊环的第⼀个节点 如果链表⽆环，则返回
    /**
     * 快慢指针
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        if(head == null ) {
            return null;
        }
        ListNode slow = head, fast = head;
        while(fast != null) {
            slow = slow.next;
            if(fast.next != null) {//防止 fast.next.next 导致空指针异常（NullPointerException）
                fast = fast.next.next;
            }else {
                return null;
            }
            if(fast == slow) {
                ListNode ptr = head;
                while(ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;//如果链表无环，fast 最终会走到链表末尾（fast == null），此时循环结束。
        //fast == null 的情况没有被 if (fast.next != null) 覆盖，需要最后的 return null 来处理。
    }

}